perm filename TUTORI.LPT[PRO,LOG] blob
sn#620882 filedate 1981-10-28 generic text, type T, neo UTF8
This file is <f.prolog>tutorial.*
A PROLOG TUTORIAL
A PROLOG TUTORIAL
A PROLOG TUTORIAL
BASED ON
BASED ON
BASED ON
USER'S GUIDE TO DECSYSTEM-10 PROLOG [3]
USER'S GUIDE TO DECSYSTEM-10 PROLOG [3]
USER'S GUIDE TO DECSYSTEM-10 PROLOG [3]
Prepared by
Ernie Davis and Udi Shapiro
December 1980
1. Introduction.
1. Introduction.
1. Introduction.
Prolog is a simple but powerful programming language
←←←←←←←←← ←←←←
developed at the University of Marseille [5] as a practical tool
for programming in logic [2, 6, 1]. From a user's point of view
the major attraction of the language is ease of programming.
Clear, readable, concise programs can be written quickly with few
errors.
Our implementation was developed in Edinburgh by Luis
M. Pereira, Fernando C. N. Pereira and David H. D. Warren, and
comprises of an interpreter and a compiler.
2. The Language.
2. The Language.
2. The Language.
A Prolog program is a collection of first-order logic
1
←←←← ←←←←
sentences (procedures) in what is called Horn-form :
P :- Q , Q ,... , Q . for n >= 0
1 2 n
←←←←←←←←←←←←←←←
1
Our Prolog implementors used ":-" instead of the more common
implication signs.
1
Where P and the Q 's are terms. for example, the following is a
i
program for computing reachability in a graph:
reachable(X,X).
reachable(X,Z) :- edge(X,Y), reachable(Y,Z).
edge(a,b).
edge(b,c).
edge(b,d).
edge(d,b).
The semantic interpretation of such a Horn sentence is: "P
is implied by the conjunction of Q ,..., Q ".
1 n
Its procedural interpretation is: "To satisfy the goal P
satisfy goals Q ,..., Q ".
1 n
When n=0 these interpretations read "P is true" or "P is
satisfied" respectively.
Note that the main functor of a term (e.g. edge in
edge(a,b)) should be adjacent to the parethesis, unlike LISP.
Also note that variable names start with Upper case letters (or
with "←") and constant names with lower case. For further
syntactic details see the manual [3].
3. Declarative and Procedural Semantics of Prolog.
3. Declarative and Procedural Semantics of Prolog.
3. Declarative and Procedural Semantics of Prolog.
One of the nice properties of Prolog is that is has a
relatively clean semantics.
To invoke a Logic program, one gives it a goal. A goal is a
sentence of the form :- P. For example
2
:- edge(a,X). or
:- reachable(a,d).
The declarative semantics of a logic program is defined as
follows:
←←←←
A goal is true if it is the head of some clause
instance and each of the goals (if any) in the body of
that clause instance is true.
When a goal is given to the Prolog interpreter, it tries to
satisfy it, in the following way, which constitutes the
procedural semantics of Prolog:
←←←←←←←
To execute a goal, the interpreter searches for the
←←←←←←← ←←←←←←←
first clause whose head matches or unifies with the goal.
The unification process [4] finds the most general
common instance of the two terms, which is unique if it
exists. If a match is found, the matching clause
instance is then activated by executing in turn, from
left to right, each of the goals (if any) in its body.
If at any time the system fails to find a match for a
goal, it backtracks, ie. it rejects the most recently
activated clause, undoing any substitutions made by the
match with the head of the clause. Next it reconsiders
the original goal which activated the rejected clause,
and tries to find a subsequent clause which also matches
the goal.
Written in Prolog, a Prolog interpreter looks like this:
execute(true) :- !.
execute((P,Q)) :- !, execute(P), execute(Q).
execute(P) :- clause(P,Q), execute(Q).
To understand how this mini-interpreter works, note that a
unit clause P. is implemented internally as P :- true, and
clause(P,Q) succeeds with a clause in the data-base whose head
3
matches P and body matches Q.
4. List Processing.
4. List Processing.
4. List Processing.
Lists are implemented in a very clean way in Prolog.
[a, b, c, d] is a list whose elements are a, b, c and d. [a | X]
is a list whose CAR is a and its CDR is X. Note that the CDR of a
list can only be a list. The term [a, b, c | X] is also legal,
and it corresponds to the list whose CAR is a, CADR is b, CADDR
is c, and CDDDR is X (clean, isn`t it?).
For example, a procedure for testing/finding membership in a
list:
member(X,[X|←]).
member(X,[←|L]) :- member(X,L).
And a procedure for finding duplicate members in lists. This
procedure illustrates how backtracking simulates two nested "for
loops".
duplicate(X,L1,L2) :- member(X,L1), member(X,L2).
And the famous append:
append([],L,L).
append([X|L1],L2,[X|L3]) :- append(L1,L2,L3).
5. Implementing a data-base in Prolog.
5. Implementing a data-base in Prolog.
5. Implementing a data-base in Prolog.
The following example almost speaks for itself. Note that
the query-user can not tell which relations are primitive and
4
which are computed.
father(abraham,isaac).
father(isaac,jacob).
father(isaac,esau).
mother(sarah,isaac).
parent(X,Y) :- father(X,Y).
parent(X,Y) :- mother(X,Y).
brother(X,Y) :- parent(Z,X), parent(Z,Y), X\==Y.
had←sex(X,Y) :- father(X,Z), mother(Y,Z).
grandmother(X,Y) :- mother(X,Z), parent(Z,Y).
6. Programming with side effects.
6. Programming with side effects.
6. Programming with side effects.
So far the examples we showed were of "pure" prolog. Every
LISP user knows that the "pure" part of the language is cleaner,
but many times more cumbersome to use. The following examples
show how by using the build-in procedures for asserting and
retracting assertions from the data base one can get the effects
of global variables:
set(Name,Value) :- retractall(variable(Name,←)),
assert(variable(Name,Value)).
add1(Name,NewValue) :- retract(variable(Name,Value)),
NewValue is Value + 1,
assert(variable(Name,NewValue)),
Using this technique and the build-in list structures one
can easily implement global stacks:
5
stack←init(Name) :- retractall(stack(Name,←)),
assert(stack(Name,[])).
push(Name,Element) :- retract(stack(Name,List)),
assert(stack(Name,[Element|List])).
pop(Name,Element) :- retract(stack(Name,[Element|List])),
assert(stack(Name,List)), !.
7. Data Entry in Prolog.
7. Data Entry in Prolog.
7. Data Entry in Prolog.
Communication with the user in Prolog is simple and easy.
For example, a procedure for asking the user a question. The
procedure succeeds if the user answer yes, fails if the user
answers no, and bothers the user forever otherwise:
ask(Question) :- repeat,
display(Question),
display(' (yes/no)?'), ttynl,
read(Answer),
(Answer=yes, !;
Answer=no, !, fail).
8. Implementing environment for Prolog.
8. Implementing environment for Prolog.
8. Implementing environment for Prolog.
The Prolog environment is good, but yet inferior to the LISP
environments. For example, the tracing utility is global and can
be invoked either from top level interpreter by executing
"trace", or by calling "trace" from an interpreted procedure.
This seems very inflexible, since if you want to stop tracing a
procedure you have to delete somehow the "trace" call from its
body. However the following shows how easy it is to implement
your own traceing facility:
trace(P) :- asserta((P :- trace, fail)).
6
Executing trace(member(←,←)) will insert
member(←,←) :- trace, fail.
as the first clause of the member procedure. Executing
member(←,←) will invoke trace and fail, and the (traced)
execution of member will proceed normally. Executing
trace(member(←,[])) will cause tracing of calls to member with an
empty list only. Implementing notrace(P) is similarly easy.
9. AI programming in Prolog.
9. AI programming in Prolog.
9. AI programming in Prolog.
All the above examples should have convinced the reader by
now that Prolog is the ideal language for AI programming. But
only to illustrate that, we show how McSam, a micro version of a
Script Applyer Mechanism can be implemented easily in Prolog.
Recall that the LISP implementation of McSam is nine pages of
code long.
A parsed story is a list of its Conceptual-Dependencies,
with some slots filled in, as (supposedly) were generated by
McEli. The following is the CD`s for the story: "John went to
leones. He ordered a Hamburger. He left."
story([[ptrans, john, john, ←, leones],
[mtrans, ←, ←, hamburger],
[ptrans, Actor, Actor, ←, ←] ]).
A script is a list of CD`s, not instantiated yet, and a list of
default names for the slots (recall that variables are
implemented internally as numbers preceded by "←", so all the
7
nice mnemonic names for script variables are lost when a script
is read in).
script(restaurant,
[ [ptrans, Actor, Actor, Earlier←place, Restaurant
[ptrans, Actor, Actor, Door, Seat],
[mtrans, Actor, Waiter, Food],
[ingest, Actor, Food, [mouth, Actor] ],
[atrans, Actor, Money, Actor, Waiter],
[ptrans, Actor, Actor, Restaurant, Gone] ],
[ [Actor, customer], [Earlier←place, place1],
[Restaurant, restaurant], [Door, door],
[Seat, seat], [Food, meal], [Waiter, waiter],
[Money, check], [Gone, place2] ] ).
For every script, there are some slot-fillers that might
trigger it:
trigger(leones, restaurant).
trigger(waiter, restaurant).
And.... here is mcsam !!!!
mcsam(Story,Script) :- find(Story,Script,Defaults),
process(Script,Story),
name←defaults(Defaults),!.
find(Story,Script,Defaults) :- filler(Slot,Story),
trigger(Slot,Name),
script(Name,Script,Default
process(Script,[]).
process([Line|Script],[Line|Story]) :- process(Script,Sto
process([Line|Script],Story) :- process(Script,Story).
filler(Slot,Story) :- member([←|Args],Story),
member(Slot,Args),
nonvar(Slot).
name←defaults([]).
name←defaults([[N,N]|L]) :- name←defaults(L).
name←defaults([[←,←]|L]) :- name←defaults(L).
This example is sort of a "low blow" to LISP, since all it
8
does is drive two unifies, the one that unifies the story with
the script, and the one that unifies the variables with their
default names. All the rest Prolog does for you. But still, we
expect McEli also to be relatively easier to program in Prolog
than in LISP. Would you like to try?
10. Some Practical Hints for Using Prolog.
10. Some Practical Hints for Using Prolog.
10. Some Practical Hints for Using Prolog.
All Prolog files are in <f.prolog>. All you need to know is
in prolog.doc . The interpreter is prolog.exe, and the compiler
is plc.exe (you might want to talk to someone who broke his teeth
using it before trying to do it yourself).
Executing the directive :-P at top level will result in
nothing (excluding side-effects) if P succeeds, and "?" if it
fails. The question directive ?-P is more useful, since it will
give you also the bindings in case of a successful termination.
In top level interpreter you can omit the "?-" and "P." will
mean a question directive. In a file you can omit the ":-" in a
unit clause, and "P." will mean "P :- true".
The correct way of using Prolog is like using UCILISP. You
write and edit procedures using a text editor, and load them
using consult('filename') the first time, and
reconsult('filename') in all other times.
A convenient alternative to the directive
consult('file1'), consult('file2'), reconsult('file3').
9
given at top level interpreter is ['file1','file2',-'file3'].
Have fun !!!
10
REFERENCES
REFERENCES
REFERENCES
[1] A. Colmerauer.
←←← ←←←←←←←←←← ←← ←←←←←←←←←←←←
Les Grammaires de Metamorphose.
Technical Report, Groupe d`Intelligence Artificielle,
Marseille-Luminy, November, 1975.
[2] Robert A. Kowalski.
←←←←← ←←← ←←←←←←← ←←←←←←←
Logic for Problem Solving.
Elsevier North Holland Inc., 1979.
[3] L. Pereira, F. Pereira and D. Warren.
←←←← ← ←←←←← ←← ←←←←←←←←← ←← ←←←←←←
User's Guide to DECsystem-10 PROLOG.
Technical Report 03/13/5570, Labortorio Nacional De
Engenharia Civil, Lisbon, September, 1978.
Provisional version.
[4] J. A. Robinson.
A Machine Oriented Logic Based on the Resolution Principle.
←←←←
JACM 12, January, 1965.
[5] P. Roussel.
←←←←←← ←←←←←← ←←←←←←←←← ←← ← ←←←←←←←←←←←
Prolog: Manuel Reference et d`Utilisation.
Technical Report, Groupe d`Intelligence Artificielle,
Marseille-Luminy, September, 1975.
[6] M. H. van-Emden.
←←←←←←←←←←← ←←←← ←←←←←←←←←← ←←←←←
Programming with Resolution Logic.
Technical Report Report CS-75-30, Dept. of Computer
Science, University of Waterloo, November, 1975.
Table of Contents
Table of Contents
Table of Contents
1. Introduction. 0
2. The Language. 0
3. Declarative and Procedural Semantics of Prolog. 1
4. List Processing. 3
5. Implementing a data-base in Prolog. 3
6. Programming with side effects. 4
7. Data Entry in Prolog. 5
8. Implementing environment for Prolog. 5
9. AI programming in Prolog. 6
10. Some Practical Hints for Using Prolog. 8